package com.sicheng.蓝桥.练习题.树状数组;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/11 19:49
 */
public class 动态前缀和 {
    int n;
    int[] a;//原数组 从1开始


    // d[x] 覆盖了以a[x]结束往前数2^k的区间长度,2^k=lowbit(x),k等于 x结尾的0的个数
    // d[6] x=(110二进制数) 覆盖了2的区间长  a[6],a[5]
    // d[7] x=(111二进制数) 覆盖了1的区间长  a[7]
    // d[5] x=(101二进制数) 覆盖了1的区间长  a[5]
    // d[4] x=(100二进制数) 覆盖了4的区间长  a[4],a[3],a[2],a[1]
    // 查询 6的前缀和a[1]~a[6]的和 二进制 110 即查询d[6],d[4]

    int[] d;//树状数组

    int lowbit(int x) {
        return x & -x;
    }

    int query(int x) {
        int res = 0;
        while (x > 0) {
            res += d[x];
            x -= lowbit(x);
        }
        return res;
    }

    void add(int x, int v) {
        while (x <= n) {
            d[x] += v;
            x += lowbit(x);
        }
    }



}
